1. Field of the Invention
The present invention relates to a representation converting apparatus, an arithmetic apparatus, a representation converting method, and a computer program product for converting an affine representation representing a 2r-th degree algebraic torus T2r(Fq) to a projective representation representing a quadratic algebraic torus T2(Fq^r).
2. Description of the Related Art
Public key cryptography actualizing secure communication without requiring a key to be shared in advance is widely used as a basic technology behind network security. Information terminals are becoming more diverse. Various schemes and protocols using a public key are being used in small devices through innovations in methods and packaging. In public key cryptography, a typical cryptographic system size is currently 1024 bits. However, a cryptographic system size considered difficult to decrypt is increasing every year, because attackers are becoming increasingly skilled with the advancement in computing devices. In public key cryptography, public key size and encrypted data size differ depending on a method being used. However, the public key size and the encrypted data size may be several times the cryptographic system size. Therefore, an increase in cryptographic system size becomes a problem for devices having insufficient memory capacity and communication bandwidth. As a result, a method has been proposed for compressing the public key size and the encrypted data size in public key cryptography (refer to, for example, K. Rubin and A Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, 349-365, 2003). A basis of the method is that, when a subset, referred to as an algebraic torus, in a set of numbers used in public key cryptography is used, a member of the set can be represented by a small number of bits. A mapping for performing conversion to the representation by a small number of bits is written as ρ and will be referred to as Rubin-Silverberg (RS) compression map. A specific example of when a encrypted data is compressed will be described. In RS compression map, computation is performed with a encrypted data c as an input. A compressed encrypted data γ is obtained by a following Expression 1.ρ(c)=γ  (1)
To convert back to a representation by an original number of bits, a reverse map of ρ is calculated. The reverse map of ρ is written as ρ−1 and will be referred to as RS decompression map. In RS decompression map, computation is performed when γ is obtained as a compressed encrypted data. c is obtained by a following Expression 2.ρ−1(γ)=c  (2)
As methods for representing the algebraic torus, an affine representation, a projective representation, and an extension field representation are known (refer to, for example, Steven Galbraith, “Disguising tori and elliptic curves”, IACR e-print Archive 2006/248, http://eprint.iacr.org/2006/248). In an algebraic torus such as this, decompression map refers to conversions of a member of the algebraic torus from the affine representation to the projective representation, from the projective representation to the extension field representation, and the affine representation to the extension field representation. On the other hand, conversions of a member of the algebraic torus from the extension field representation to the projective representation, from the projective representation to the affine representation, and the extension field representation to the affine representation are equivalent to compression map. Compression map and decompression map using the algebraic torus such as those described above can also be applied to signatures in digital signatures and exchange messages in key exchange schemes, in addition to public keys and encrypted datas in public key cryptography. For example, in R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen encrypted data attack”, CRYPTO'98, LNCS 1462, pp. 13-25, 1998, El Gamal encryption and Diffie-Hellman (DH) key exchange using an algebraic torus over a prime field are proposed. In R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen encrypted data attack”, CRYPTO'98, LNCS 1462, pp. 13-25, 1998, Cramer-Shoup cryptosystem is proposed. In the Cramer-Shoup cryptosystem, security in a standard model is proven. For example, plain data and encrypted data are members of a prime order subgroup G of a multiplicative group G˜ of a prime field of which an order is a prime number. At this time, the plain data and the encrypted data are represented by the multiplicative group G˜ of the prime field. A member of a small group G is needlessly represented by a large group G˜. Therefore, when G˜ in the Cramer-Shoup cryptosystem serves as a multiplicative group of an extension field, and G serves as an algebraic torus, the plain data and the encrypted data are members of G and can be represented by G. Needless representation can be eliminated. When G˜ in the Cramer-Shoup cryptosystem serves as the multiplicative group of an extension field, and G is a secure subgroup of an algebraic torus, needless representation can be reduced. Encryption that can eliminate or reduce needless representation through application of an algebraic torus is not limited to the El Gamal encryption, the DH key exchange, and the Cramer-Shoup cryptosystem.
The RS compression map and the RS decompression map compress and decompress an algebraic torus T6(Fq) defined over the prime field. Here, the cryptographic system size is 2048 bits. A size of p regarding a p-order (prime order) prime field is at least “ceil(2048/6)=342” bits. Ceil(x) is referred to as a ceiling function and returns a least integer that is equal to or greater than x. The size of p exceeds a word length, such as 32 bits and 64 bits of a computing device. Calculation on the algebraic torus is actualized by calculation on a finite field on which the algebraic torus is defined or a basic field thereof. Therefore, regarding an algebraic torus Tn(Fq) defined over a prime field Fq, calculation on the algebraic torus Tn(Fq) is actualized using calculation on the prime field Fq. When a size of the prime field exceeds the word length, calculation becomes difficult to perform using the computing device.
Therefore, to reduce the size of the prime field, use of an algebraic torus T6(Fq^r) defined over an extension field Fq^r is considered. The size of p of an extension field of a p^r-th order is at least “ceil(2048/(6*r))”. The size of p can be reduced through adjustment of an extension degree r. For example, when “r=24”, p is 15 bits. When “r=27”, p is 13 bits. At this time, the RS compression map and the RS decompression map cannot be used with an extension degree such as this. In the RS method, a sixth degree extension field is configured using a cyclotomic field or a subfield of a cyclotomic field as a quadratic extension of a cubic extension. Conditions are strict for a cyclotomic polynomial that is a modulus of the cyclotomic field to become irreducible over an extension field. The conditions may contradict conditions imposed on the extension degree r to configure an algebraic torus of a prime order.
On the other hand, regarding compression map and decompression map of an algebraic torus defined over an extension field, for example, a mapping method proposed in R. Granger, D. Page, and M. Stam, “On Small Characteristic Algebraic Tori in Pairing Based Cryptography”, LMS Journal of Computation and Mathematics, 9, pp. 64-85, 2006 is known. Compression map and decompression map based on the proposed mapping method are respectively referred to as Granger-Page-Stam (GPS) compression map and GPS decompression map. In the GPS method, a sixth degree extension field is configured as a quadratic extension of a cubic extension, in a manner similar to that of a Duursma-Lee method (a Tate pairing computation method). In the Duursma-Lee method, “p=3”.
In this case, when r is retrieved under the conditions imposed on the extension degree r to configure an algebraic torus of a prime order, a suitable parameter cannot be found. In other words, when the torus defined over the extension field is used and the order thereof is a prime number, the compression map and the decompression map described in K. Rubin and A Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, 349-365, 2003, and R. Granger, D. Page, and M. Stam, “On Small Characteristic Algebraic Tori in Pairing Based Cryptography”, LMS Journal of Computation and Mathematics, 9, pp. 64-85, 2006 may not be usable. Moreover, when a common decompression map method is used, processing load of calculation processes, such as an encryption process and a decryption process, after conversion from the affine representation to the projective representation may increase.